package org.alis.smallcc.algorithm;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;

/**
 * 
 * 贪心算法之背包问题 假设有一个背包最大可以装 150kg 物品 某物品 重量 价值(元) 性价比(单位重量的价格) 
 * a 35kg 10 10/35 
 * b 30kg 40 40/30 
 * c 60kg 30 30/60 
 * d 50kg 50 50/50 
 * e 40kg 35 35/40 
 * f 10kg 40 40/10
 * g 25kg 30 30/25
 * 
 * 求：背包可以装入的最大价值？
 * 
 * @author luochuan
 */
public class Knapsack {

	/**
	 * 寻解
	 * 
	 * @param capacity 背包容量
	 * @param weight   物品重量
	 * @param price    物品的单价
	 */
	private void knapsackGreedy(int capacity, int[] weight, int[] price) {
		// 总物品的长度
		int size = weight.length;
		// 物品的性价比
		double[] performance = new double[size];
		// 给物品的性价比下标记录一下
		int[] index = new int[size];
		// 开始给默认的下班
		for (int cursor = 0, count = size; cursor < count; cursor++) {
			index[cursor] = cursor;
			performance[cursor] = (double)price[cursor]/ (double) weight[cursor] ;
		}
		// 使用冒泡排序换排序权重
		for (int i = 0; i < size - 1; i++) {
			for (int j = i + 1; j < size; j++) {
				if (performance[i] < performance[j]) {
					// 开始交换
					double tempPerformance = performance[i];
					performance[i] = performance[j];
					performance[j] = tempPerformance;

					// 将排序后性价比的下标更新为性价比排序后的位置
					int tempIndex = index[i];
					index[i] = index[j];
					index[j] = tempIndex;
				}
			}
		}
		// 将排序好的重量和价值分别保存到数组
		int[] w = new int[size];
		int[] p = new int[size];
		for (int i = 0; i < size; i++) {
			w[i] = weight[index[i]];
			p[i] = price[index[i]];
		}

		// 将物品装入背包
		// 记录哪些物品已经被装入背包 0 没有装入背包 1 代表已经装入背包
		int[] n = new int[size];
		// 如果当前容量是零
		int currentCapacity = 0;
		for (int i = 0; i < size; i++) {
			if (w[i] <= capacity) {
				// 还能装
				// 表示这个物品被装进袋子了
				n[i] = 1;
				currentCapacity += p[i];
				capacity -= w[i];
				System.out.println("物品：" + w[i] + " 放进了背包");
			}
		}
		List<Integer> wList = new ArrayList<>();
		List<Double> pList = new ArrayList<>();
		for(int i=0;i<n.length;i++) {
			if(n[i]==1) {
				wList.add(w[i]);
				pList.add(performance[i]);
			}
		}
		
		System.out.println("放入的物品分别是:"+wList.stream().map(String::valueOf).collect(Collectors.joining(",","[","]")));
		System.out.println("放入的物品的性价比分别是:"+pList.stream().map(String::valueOf).collect(Collectors.joining(",","[","]")));
		System.out.println("总共放下的物品的数量为：" + Arrays.toString(n));
		System.out.println("最大价值为：" + currentCapacity);
	}

	/**
	 * 主测试方法
	 * 
	 * @param args
	 */
	public static void main(String[] args) {
		Knapsack np = new Knapsack();
		int capacity = 150;
		int[] weight = new int[] { 35, 30, 60, 50, 40, 10, 25 };
		int[] price = new int[] { 10, 40, 30, 50, 35, 40, 30 };
		np.knapsackGreedy(capacity, weight, price);
	}
}
